package 算法模板;

import java.util.Arrays;

/**
 * 希尔排序，也被称为递减增量排序，是简单插入排序的一种改进版本。
 * <p>
 * 在插入排序中，有可能较小的元素在比较靠后的位置，比如：
 * {2, 5, 5, 3, 6, 6, 9, 1}
 * 这样到1的位置时，之前的元素都要往后移一位，在大数据下这样的效率
 * 显然很低，所以需要把较小的数往前移
 * <p>
 * 思想：
 * 将整个数组按照相间隔的元素进行分组，然后进行直接插入排序
 * 分组方法: 数组长度/2，当间隔为1时，进行最后的直接插入排序
 * <p>
 * 例子：{2, 5, 5, 3, 6, 6, 9, 1}
 * interval：8/2=4
 * 从索引i=4开始，前面的interval=4的元素与之比较，如果大于则将前面的值复制到当前元素，i++
 * 排序后：{2, 5, 5, 1, 6, 6, 9, 3}
 * interval：4/2=2
 * 从索引i=2开始，前面的interval=2的元素与之比较，如果大于则将前面的值复制到当前元素，i++
 */
public class 希尔排序 {

    public static void main(String[] args) {

        int[] nums = {2, 5, 2, 6, 3, -1, 3, 55, 3};
        shellSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void shellSort(int[] nums) {
        int len = nums.length;
        for (int interval = len / 2; interval > 0; interval = interval / 2) {
            //从interval的位置开始比较前面相隔interval的元素是否大于当前元素，决定是否交换位置
            for (int i = interval; i < len; i++) {
                //保存需要插入的元素
                int readyInsertNum = nums[i];
                int right = i;
                //准备交换的元素必须大于等于间隔，因为会判断当前元素前面interval个元素
                while (right >= interval && nums[right - interval] > readyInsertNum) {
                    //如果前面interval个元素大于当前元素，前面元素交换到当前位置
                    nums[right] = nums[right - interval];
                    right = right - interval;
                }
                //插入保存的元素
                nums[right] = readyInsertNum;
            }
        }
    }

}
